package lc20240501;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Demo1 {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }

        int wordLen = words[0].length();
        int totalLen = wordLen * words.length;

        Map<String, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - totalLen; i++) {
            String substr = s.substring(i, i + totalLen);
            if (isConcatenation(substr, wordCount, wordLen)) {
                result.add(i);
            }
        }

        return result;
    }

    private static boolean isConcatenation(String s, Map<String, Integer> wordCount, int wordLen) {
        Map<String, Integer> temp = new HashMap<>();
        for (int i = 0; i < s.length(); i += wordLen) {
            String word = s.substring(i, i + wordLen);
            temp.put(word, temp.getOrDefault(word, 0) + 1);
        }
        return temp.equals(wordCount);
    }

    public static void main(String[] args) {
        String s="wordgoodgoodgoodbestword";
        String[] words={"word","good","best","word"};
        System.out.println(findSubstring(s, words));
    }

}
